from typing import List


# 63. 不同路径 II
# 时间复杂度：O(mn)，其中 m 为网格的行数，n 为网格的列数。我们只需要遍历所有网格一次即可。
# 空间复杂度：O(mn)。
#
# 利用滚动数组优化，我们可以只用 O(m) 大小的空间来记录当前行的 f 值。
def uniquePathsWithObstacles(obstacleGrid: List[List[int]]) -> int:
    # 行
    m = len(obstacleGrid)
    # 列
    n = len(obstacleGrid[0])
    # 初始化 dp 数组，起始位置为 1
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    dp[1][1] = 0 if obstacleGrid[0][0] == 1 else 1
    # 填 dp[1][x] 上面的路径
    for i in range(2, n + 1):
        dp[1][i] = 0 if obstacleGrid[0][i - 1] == 1 else dp[1][i - 1]
    # 填 dp[x][1] 上面的路径
    for j in range(2, m + 1):
        dp[j][1] = 0 if obstacleGrid[j - 1][0] == 1 else dp[j - 1][1]

    # 填其它位置的路径
    for row in range(2, m + 1):
        for column in range(2, n + 1):
            dp[row][column] = 0 if obstacleGrid[row - 1][column - 1] == 1 else dp[row - 1][column] + dp[row][column - 1]

    return dp[m][n]


obstacleGrid_1 = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
result = uniquePathsWithObstacles(obstacleGrid_1)
print(f"result:{result}")

obstacleGrid_1 = [[0, 1], [0, 0]]
result = uniquePathsWithObstacles(obstacleGrid_1)
print(f"result:{result}")

obstacleGrid_1 = [[0, 0, 1], [0, 1, 0], [0, 0, 0]]
result = uniquePathsWithObstacles(obstacleGrid_1)
print(f"result:{result}")

obstacleGrid_1 = [[0, 0, 0], [0, 1, 0], [0, 0, 0], [0, 0, 0]]
result = uniquePathsWithObstacles(obstacleGrid_1)
print(f"result:{result}")
